package solution;

import common.Node;
import common.TreeNode;

import java.util.*;
import java.util.List;

/**
 * @author zhangmin
 * @create 2021-08-07 12:57
 */
public class Solution_4tree {

    /*===========================================================================================================================
     *二叉树 226. 翻转二叉树
     * invertTree(TreeNode root)表示将root为根的树左右翻转
     * */
    public TreeNode invertTree(TreeNode root) {
        if (root==null){
            return null;
        }
        // 交换root的两个子树
        TreeNode t=root.right;
        root.right=root.left;
        root.left=t;
        //递归将左右子树都进行翻转
        invertTree(root.left);
        invertTree(root.right);

        return root;
    }

    /*===========================================================================================================================
     *二叉树 116. 填充每个节点的下一个右侧节点指针
     *填充完美二叉树的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
     * connectTwoNode(Node node1,Node node2)表示跨越node1子树和node2子树，将两个子树相连
     * */
    public Node connect(Node root) {
        if(root==null) return null;
        connectTwoNode(root.left,root.right);
        return root;
    }

    public void connectTwoNode(Node node1, Node node2){
        if (node1==null||node2==null) return;
        node1.next=node2;
        //将相同父节点的两个子节点相连
        connectTwoNode(node1.left,node1.right);
        connectTwoNode(node2.left,node2.right);
        //将不同父节点的两个子节点相连
        connectTwoNode(node1.right,node2.left);
    }

    /*===========================================================================================================================
     *二叉树 114. 二叉树展开为链表
     * flatten(TreeNode root)表示将root为根的子树拉平为链表
     * */
    public void flatten(TreeNode root) {
        //base case
        if (root==null)
            return;
        //递归将左右子树展开
        flatten(root.left);
        flatten(root.right);

        //将展开的左子树合并到右子树上
        TreeNode leftNode=root.left;
        TreeNode rightNode=root.right;
        root.right=leftNode;
        root.left=null;
        TreeNode p=root;
        while (p.right!=null){
            p=p.right;
        }
        p.right=rightNode;
    }

    /*===========================================================================================================================
     *二叉树 654. 最大二叉树
     * 给定一个不含重复元素的整数数组 nums 。一个以此数组直接递归构建的 最大二叉树 定义如下：
        二叉树的根是数组 nums 中的最大元素。
        左子树是通过数组中 最大值左边部分 递归构造出的最大二叉树。
        右子树是通过数组中 最大值右边部分 递归构造出的最大二叉树。
        返回有给定数组 nums 构建的 最大二叉树 。
     */
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return build(nums,0,nums.length-1);
    }
    TreeNode build(int[] nums,int l,int r){
        if (l>r)return null;
        //找到l到r之间最大值及其下标
        int max=Integer.MIN_VALUE;
        int maxIndex=l;
        for (int i = l; i <=r; i++) {
            if (max<nums[i]){
                max=nums[i];
                maxIndex=i;
            }
        }
        //构造根节点
        TreeNode root=new TreeNode(max);
        root.left=build(nums,l,maxIndex-1);
        root.right=build(nums,maxIndex+1,r);
        return root;
    }

    /*===========================================================================================================================
     *二叉树 105. 从前序与中序遍历序列构造二叉树
     * */
    public TreeNode buildTree1(int[] preorder, int[] inorder) {
        return build1(preorder,0,preorder.length-1,inorder,0,inorder.length-1);
    }

    public TreeNode build1(int[] preorder,int preLeft,int preRight,
                           int[] inorder,int inLeft,int inRight){
        if (preLeft>preRight) return null;
        //root节点对应的值是preorder的第一个元素
        int rootVal=preorder[preLeft];
        TreeNode root=new TreeNode(rootVal);
        int index=inLeft;
        //找到root值在inOeder中的索引，确定左子树的元素个数
        for (int i = inLeft; i <=inRight ; i++) {
            if (inorder[i]==rootVal){
                index=i; break;
            }
        }

        int leftSize=index-inLeft;
        root.left=build1(preorder,preLeft+1,preLeft+leftSize, inorder,inLeft,index-1);
        root.right=build1(preorder,preLeft+leftSize+1,preRight,inorder,index+1,inRight);
        return root;
    }

    /*===========================================================================================================================
     *二叉树 106. 从中序与后序遍历序列构造二叉树
     * */
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        return build2(postorder,0,postorder.length-1,inorder,0,inorder.length-1);
    }
    public TreeNode build2(int[] postorder,int postLeft,int postRight,
                             int[] inorder,int inLeft,int inRight){
        if (inLeft>inRight) return null;
        //root节点对应的值是postorder的最后一个元素
        int rootVal=postorder[postRight];
        TreeNode root=new TreeNode(rootVal);
        int index=inLeft;
        //找到root值在inOeder中的索引，确定左子树的元素个数
        for (int i = inLeft; i <=inRight ; i++) {
            if (inorder[i]==rootVal){
                index=i; break;
            }
        }

        int leftSize=index-inLeft;
        root.left=build2(postorder,postLeft,postLeft+leftSize-1, inorder,inLeft,index-1);
        root.right=build2(postorder,postLeft+leftSize,postRight-1,inorder,index+1,inRight);
        return root;
    }

    /*===========================================================================================================================
     *二叉树 652. 寻找重复的子树
     * 给定一棵二叉树，返回所有重复的子树。对于同一类的重复子树，你只需要返回其中任意一棵的根结点即可。两棵树重复是指它们具有相同的结构以及相同的结点值。
     * */
    //map记录没子树结构出现的次数，res记录重复子树的根节点
    HashMap<String,Integer> map=new HashMap<>();
    List<TreeNode> res=new LinkedList<>();
    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        traverse(root);
        return res;
    }
    //traverse(TreeNode root)将root根的子树序列化以后判断是否出现过
    public String traverse(TreeNode root){
        if (root==null)
            return "#";
        String left=traverse(root.left);
        String right=traverse(root.right);
        String subTree=left+","+right+","+root.val;
        int cnt=map.getOrDefault(subTree,0);
        if (cnt==1){
            res.add(root);
        }
        map.put(subTree,cnt+1);
        return subTree;
    }

    /*===========================================================================================================================
     *BST（二叉搜索树）230. 二叉搜索树中第K小的元素
     * //1.先中序遍历得到升序排列，找到第k个即可
     * //2.需要在二叉树节点中维护额外信息。每个节点需要记录，以自己为根的这棵二叉树有多少个节点。
     * */
    int res1=0;
    int rank=0;
    public int kthSmallest(TreeNode root, int k) {
        traverse(root,k);
        return res1;
    }
    public void traverse(TreeNode root,int k){
        if (root==null) return;
        traverse(root.left,k);
        rank++;
        if (k==rank){
            res1=root.val;
            return;
        }
        traverse(root.right,k);
    }

    /*===========================================================================================================================
     *BST（二叉搜索树）538,1038. 把二叉搜索树转换为累加树
     * 使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。
     * 利用 BST 的中序遍历特性。从大到小降序打印 BST 节点的值，如果维护一个外部累加变量sum，然后把sum赋值给 BST 中的每一个节点
     * */
    int sum=0;
    public TreeNode convertBST(TreeNode root) {
        traverse1(root);
        return root;
    }
    //从大到小遍历树
    public void traverse1(TreeNode root){
        if (root==null) return;
        // 先递归遍历右子树
        traverse1(root.right);
        sum=sum+root.val;
        // 将 BST 转化成累加树
        root.val=sum;
        traverse1(root.left);
    }
    /*===========================================================================================================================
     *BST（二叉搜索树）98. 验证二叉搜索树
     * */
    public boolean isValidBST1(TreeNode root) {
        return isValidBST(root,null,null);
    }
    //* 限定以 root 为根的子树节点必须满足 max.val > root.val > min.val
    public boolean isValidBST(TreeNode root,TreeNode min,TreeNode max){
        if (root==null) return true;
        if (min!=null&&root.val<=min.val) return false;
        if (max!=null&&root.val>=max.val) return false;
        return isValidBST(root.left,min,root)&&isValidBST(root.right,root,max);
    }
    /*===========================================================================================================================
     *BST（二叉搜索树）700. 二叉搜索树中的搜索
     * */
    public TreeNode searchBST(TreeNode root, int val) {
        if (root==null) return null;
        if (root.val==val)
            return root;
        else if (root.val<val) return searchBST(root.right,val);
        else return searchBST(root.left,val);
    }
    /*===========================================================================================================================
     *BST（二叉搜索树）701. 二叉搜索树中的插入操作
     * */
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if (root==null) return new TreeNode(val);
        if (root.val<val) root.right=insertIntoBST(root.right,val);
        if (root.val>val )root.left=insertIntoBST(root.left,val);
        return root;
    }
    /*===========================================================================================================================
     *BST（二叉搜索树）450. 删除二叉搜索树中的节点
     * */
    public TreeNode deleteNode(TreeNode root, int key) {
        if (root==null) return null;
        if (root.val==key){
            //删除节点
            //1.恰好是末端节点，两个子节点都为空，那么它可以当场去世了。
            //2.只有一个非空子节点，那么它要让这个孩子接替自己的位置。
            if (root.left==null){
                return root.right;
            }
            if (root.right==null) return root.left;
            //3.有两个子节点，麻烦了，为了不破坏 BST 的性质，A 必须找到左子树中最大的那个节点，或者右子树中最小的那个节点来接替自己
            TreeNode minNode=getMinNode(root.right);
            root.val=minNode.val;
            root.right=deleteNode(root.right,minNode.val);

        }else if (root.val<key){
            root.right=deleteNode(root.right,key);
        }else if (root.val>key){
            root.left=deleteNode(root.left,key);
        }
        return root;
    }
    TreeNode getMinNode(TreeNode root){
        // BST 最左边的就是最小的
        while (root.left!=null) root=root.left;
        return root;
    }

    /*===========================================================================================================================
     *BST（二叉搜索树）96. 不同的二叉搜索树
     * 给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？
     * */
    int[][] memo;
    public int numTrees(int n) {
        memo=new int[n+1][n+1];
        return count(1,n);
    }
    /* 计算闭区间 [l, r] 组成的 BST 个数 */
    int count(int l,int r){
        if (l>r) return 1;
        // 查备忘录
        if (memo[l][r]!=0)return memo[l][r];
        int res=0;
        for (int i = l; i <= r; i++) {
            // i 的值作为根节点 root
            int left=count(l,i-1);
            int right=count(i+1,r);
            res+=left*right;
        }
        // 将结果存入备忘录
        memo[l][r]=res;
        return res;
    }

    /*===========================================================================================================================
     *BST（二叉搜索树）95. 不同的二叉搜索树 II
     * 给你一个整数 n ，请你生成并返回所有由 n 个节点组成且节点值从 1 到 n 互不相同的不同 二叉搜索树 。可以按 任意顺序 返回答案。
     * */

    public List<TreeNode> generateTrees(int n) {
        return build(1,n);
    }
    /* 生成闭区间 [l, r] 组成的 BST */
    List<TreeNode> build(int l,int r){
        List<TreeNode> res=new ArrayList<>();
        if (l>r) {
            res.add(null);
            return res;
        }
        // 1、穷举 root 节点的所有可能。
        for (int i = l; i <= r; i++) {
            // 2、递归构造出左右子树的所有合法 BST。
            List<TreeNode> letfTree=build(l,i-1);
            List<TreeNode> rightTree=build(i+1,r);
            // 3、给 root 节点穷举所有左右子树的组合。
            for (TreeNode left:letfTree){
                for (TreeNode right:rightTree){
                    TreeNode root=new TreeNode(i);
                    root.left=left;
                    root.right=right;
                    res.add(root);
                }
            }
        }
        return res;
    }


    /*===========================================================================================================================
     *BST（二叉搜索树）1373. 二叉搜索子树的最大键值和
     * 使用后序遍历提高效率
     * 那么我们想计算子树中 BST 的最大和，站在当前节点的视角，需要做什么呢？
        1、我肯定得知道左右子树是不是合法的 BST，如果这俩儿子有一个不是 BST，以我为根的这棵树肯定不会是 BST，对吧。
        2、如果左右子树都是合法的 BST，我得瞅瞅左右子树加上自己还是不是合法的 BST 了。因为按照 BST 的定义，
            当前节点的值应该大于左子树的最大值，小于右子树的最小值，否则就破坏了 BST 的性质。
        3、因为题目要计算最大的节点之和，如果左右子树加上我自己还是一棵合法的 BST，也就是说以我为根的整棵树是一棵 BST，
            那我需要知道我们这棵 BST 的所有节点值之和是多少，方便和别的 BST 争个高下，对吧。
     * */
    int maxsum=0;
    public int maxSumBST(TreeNode root) {
        traverse2(root);
        return maxsum;
    }
    /*traverse(root) 返回一个大小为 4 的 int 数组，我们暂且称它为 res，其中：
    res[0] 记录以 root 为根的二叉树是否是 BST，若为 1 则说明是 BST，若为 0 则说明不是 BST；
    res[1] 记录以 root 为根的二叉树所有节点中的最小值；
    res[2] 记录以 root 为根的二叉树所有节点中的最大值；
    res[3] 记录以 root 为根的二叉树所有节点值之和。
    其实这就是把之前分析中说到的几个值放到了 res 数组中，最重要的是，我们要试图通过 left 和 right 正确推导出 res 数组。*/
    int[] traverse2(TreeNode root) {
        if (root==null){
            return new int[]{1,Integer.MAX_VALUE,Integer.MIN_VALUE,0};
        }
        // 递归计算左右子树
        int[] letfRes=traverse2(root.left);
        int[] rightRes=traverse2(root.right);

        /******* 后序遍历位置 *******/
        int[] res=new int[4];
        // 这个 if 在判断以 root 为根的二叉树是不是 BST
        if (letfRes[0]==1&&rightRes[0]==1&&root.val>letfRes[2]&&root.val<rightRes[1]){
            //当前以root为根的子树是BST
            res[0]=1;
            // 计算以 root 为根的这棵 BST 的最小值
            res[1]=Math.min(letfRes[1],root.val);
            // 计算以 root 为根的这棵 BST 的最大值
            res[2]=Math.max(rightRes[2],root.val);
            // 计算以 root 为根的这棵 BST 所有节点之和
            res[3]=letfRes[3]+rightRes[3]+root.val;
            // 更新全局变量
            maxsum = Math.max(maxsum, res[3]);
        }else {
            // 以 root 为根的二叉树不是 BST
            // 其他的值都没必要计算了，因为用不到
            res[0]=0;
        }
        return res;
    }

    /*===========================================================================================================================
     *BST（二叉搜索树）297. 二叉树的序列化与反序列化
     * 请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，
     * 你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。
     * 1.前序遍历
     * */
    /*前序遍历序列化主程序*/
    // Encodes a tree to a single string.
    public String serializePre(TreeNode root) {
        StringBuffer sb=new StringBuffer();
        serializePre(root,sb);
        return sb.toString();
    }
    /*前序遍历序列化，辅助*/
    public void serializePre(TreeNode root,StringBuffer sb){
        if (root==null){
            sb.append("#").append(",");
            return ;
        }
        sb.append(root.val).append(",");
        serializePre(root.left,sb);
        serializePre(root.right,sb);
    }

    /*前序遍历反序列化主程序*/
    // Decodes your encoded data to tree.
    public TreeNode deserializePre(String data) {
        List<String> nodes=new LinkedList<>();
        String[] node=data.split(",");
        for (String n:node) {
            nodes.add(n);
        }
        return deserializePre(nodes);
    }
    /*前序遍历反序列化，辅助*/
    public TreeNode deserializePre(List<String> nodes){
        if (nodes.isEmpty()){
            return null;
        }
        String first=nodes.remove(0);
        if (first.equals("#")) return null;
        TreeNode root=new TreeNode(Integer.parseInt(first));

        root.left=deserializePre(nodes);
        root.right=deserializePre(nodes);
        return root;

    }

    /*===========================================================================================================================
     *BST（二叉搜索树）297. 二叉树的序列化与反序列化
     * 2.后序遍历
     * */
    /*后序遍历序列化主程序*/
    // Encodes a tree to a single string.
    public String serializePosOrder(TreeNode root) {
        StringBuffer sb=new StringBuffer();
        serializePosOrder(root,sb);
        return sb.toString();
    }
    /*后序遍历序列化，辅助*/
    public void serializePosOrder(TreeNode root,StringBuffer sb){
        if (root==null){
            sb.append("#").append(",");
            return ;
        }
        serializePosOrder(root.left,sb);
        serializePosOrder(root.right,sb);
        sb.append(root.val).append(",");
    }

    /*后序遍历反序列化主程序*/
    // Decodes your encoded data to tree.
    public TreeNode deserializePos(String data) {
        List<String> nodes=new LinkedList<>();
        String[] node=data.split(",");
        for (String n:node) {
            nodes.add(n);
        }
        return deserializePos(nodes);
    }
    /*后序遍历反序列化，辅助*/
    public TreeNode deserializePos(List<String> nodes){
        if (nodes.isEmpty()){
            return null;
        }
        String last=nodes.remove(nodes.size());
        if (last.equals("#")) return null;
        TreeNode root=new TreeNode(Integer.parseInt(last));
        root.right=deserializePos(nodes);
        root.left=deserializePos(nodes);
        return root;

    }
    /*===========================================================================================================================
     *BST（二叉搜索树）297. 二叉树的序列化与反序列化
     * 3.层序遍历
     * */
    public String serializeLevelOrder(TreeNode root) {
        if(root==null) return "";
        StringBuffer sb=new StringBuffer();
        Queue<TreeNode> q=new LinkedList<>();
        q.offer(root);
        while (!q.isEmpty()){
            TreeNode cur=q.poll();
            if (cur==null){
                sb.append("#").append(",");
                continue;
            }
            sb.append(cur.val).append(",");
            q.offer(cur.left);
            q.offer(cur.right);
        }
        return sb.toString();
    }
    public TreeNode deserializeLevel(String data) {
        if (data==null)return null;
        String[] nodes=data.split(",");
        TreeNode root=new TreeNode(Integer.parseInt(nodes[0]));
        Queue<TreeNode> q=new LinkedList<>();
        q.offer(root);
        for (int i = 1; i <nodes.length ; i++) {
            TreeNode parent=q.poll();
            String left=nodes[i++];
            if (!left.equals("#")){
                parent.left=new TreeNode(Integer.parseInt(left));
                q.offer(parent.left);
            }else {
                parent.left=null;
            }

            String right=nodes[i++];
            if (!right.equals("#")){
                parent.right=new TreeNode(Integer.parseInt(right));
                q.offer(parent.right);
            }else {
                parent.right=null;
            }
        }
        return root;
    }

    /*===========================================================================================================================
     *236. 二叉树的最近公共祖先
     * root节点确定了一棵二叉树，p和q是这这棵二叉树上的两个节点，让你返回p节点和q节点的最近公共祖先节点。
     * */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        //base case1.root为空
        if (root==null)return null;
        //base case2.root本身是p或者q则不管另一个是否在root的子树中都一定会返回root
        if (root==q||root==p) return root;
        TreeNode letf=lowestCommonAncestor(root.left,p,q);
        TreeNode right=lowestCommonAncestor(root.right,p,q);

        //后序遍历位置：而后序遍历是从下往上，就好比从p和q出发往上走，第一次相交的节点就是这个root---保证返回的是最近的公共祖先
        //情况1：p，q分别在两个子树中
        if (letf!=null&&right!=null){
            return root;
        }
        //情况2：p和q都不在root中
        if (letf==null&&right==null){
            return null;
        }
        //情况3：p或q有一个在某个子树中
        return letf!=null? letf:right;
    }
    /*===========================================================================================================================
     *求二叉树的节点个数
     * */
    public int countNodes1(TreeNode root){
        if (root==null) return 0;
        return 1+countNodes1(root.left)+countNodes1(root.right);
    }

    /*===========================================================================================================================
     *求满二叉树的节点个数
     * */
    public int countNodes2(TreeNode root){
        int h=0;
        // 计算树的高度
        while (root!=null){
            root=root.left;
            h++;
        }
        // 节点总数就是 2^h - 1
        return (int)Math.pow(2,h)-1;
    }

    /*===========================================================================================================================
     *222. 完全二叉树的节点个数
     * 完全二叉树，每一层都是紧凑靠左排列的：
     * 满二叉树，是一种特殊的完全二叉树，每层都是是满的，像一个稳定的三角形
     * 算法的时间复杂度是 O(logN*logN):
     *                  关键点在于，这两个递归只有一个会真的递归下去，另一个一定会触发 hl == hr 而立即返回，不会递归下去。
     *                  因为一棵完全二叉树的两棵子树，至少有一棵是满二叉树：
     * */
    public int countNodes3(TreeNode root) {
        TreeNode lNode=root,rNode=root;
        //记录左右子树高度
        int lh=0,rh=0;
        while (lNode!=null){
            lNode=lNode.left;
            lh++;
        }
        while (rNode!=null){
            rNode=rNode.right;
            rh++;
        }
        if (lh==rh){
            // 如果左右子树的高度相同，则是一棵满二叉树
            return (int)Math.pow(2,lh)-1;
        }
        // 如果左右高度不同，则按照普通二叉树的逻辑计算
        return 1+countNodes3(root.left)+countNodes3(root.right);
    }

    /*===========================================================================================================================
     *二叉树的最大深度
     * 1.递归
     * 2.BFS：逐层统计
     * 3.DFS
     * */
    /*public int maxDepth(TreeNode root) {
        if (root== null){
            return 0;
        }
        int res=Math.max(maxDepth(root.left),maxDepth(root.right))+1;
        return res;
    }*/
    public int maxDepth(TreeNode root) {
        if (root== null){
            return 0;
        }
        //创建队列，记录每一层的元素
        Deque<TreeNode> deque=new LinkedList<>();
        deque.push(root);
        int res=0;
        while (!deque.isEmpty()){
            int size=deque.size();
            while (size-->0){
                TreeNode cur=deque.poll();
                if (cur.left!=null)
                    deque.addLast(cur.left);
                if (cur.right!=null)
                    deque.addLast(cur.right);
            }
            res++;
        }
        return res;
    }



    /*===========================================================================================================================
     *验证二叉搜索树
     * 1.使用中序遍历
     * 2.递归
     * */
    TreeNode preNode;
/*    public boolean isValidBST(TreeNode root) {
        if (root==null) return true;
        if (!isValidBST(root.left))
            return false;
        if (preNode!=null&&preNode.val>=root.val)
            return false;
        preNode=root;
        if (!isValidBST(root.right))
            return false;
        return true;
    }*/
    public boolean isValidBST(TreeNode root) {
        if (root==null) return true;
        if (root.left!=null&&root.val<=root.left.val||root.right!=null&&root.val>=root.right.val)
            return false;
        return isValidBST(root.left)&&isValidBST(root.right);
    }
    public void midOrder(TreeNode root){
        if (root==null) return;
        midOrder(root.left);
        System.out.println(root.val);
        midOrder(root.right);
    }


    /*===========================================================================================================================
     *对称二叉树
     * 1.递归
     * 2.中序遍历，判断是否为回文(满二叉树)
     * */
    public boolean isSymmetric(TreeNode root) {
        if (root==null)
            return true;
        return isSymmetricLandR(root.left,root.right);
    }
    public boolean isSymmetricLandR(TreeNode left,TreeNode right){
        //如果左右子节点都为空，说明当前节点是叶子节点，返回true
        if (left==null&&right==null)
            return true;
        if (left==null||right==null||left.val!=right.val)
            return false;
        return isSymmetricLandR(left.left,right.right)&&isSymmetricLandR(left.right,right.left);
    }

    /*===========================================================================================================================
     *二叉树的层序遍历
     * 1.BFS：用对列
     * */
    public List<List<Integer>> levelOrder(TreeNode root) {
        if(root==null)
            return new ArrayList<>();
        Queue<TreeNode> queue=new LinkedList<>();
        List<List<Integer>> res=new ArrayList<>();
        queue.add(root);
        while (!queue.isEmpty()){
            //BFS打印，levelNodeNum表示的是每层的结点数
            int levelNodeNum=queue.size();
            System.out.println("levelNodeNum="+levelNodeNum);
            //list存储每一层的节点值
            List<Integer> list=new ArrayList<>();
            for (int i = 0; i < levelNodeNum; i++) {
                TreeNode node=queue.poll();
                list.add(node.val);
                System.out.println(node.val);
                if (node.left!=null)
                    queue.add(node.left);
                if (node.right!=null)
                    queue.add(node.right);
            }
            res.add(list);
        }
        return res;
    }
    //层序遍历框架：
    void traverseLevelOrder(TreeNode root) {
        if (root == null) return;
        // 初始化队列，将 root 加入队列
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);

        while (!q.isEmpty()) {
            TreeNode cur = q.poll();

            /* 层级遍历代码位置 */
            System.out.println(root.val);
            /*****************/

            if (cur.left != null) {
                q.offer(cur.left);
            }

            if (cur.right != null) {
                q.offer(cur.right);
            }
        }
    }

    /*===========================================================================================================================
     *将有序数组转换为二叉搜索树
     * 1.递归:每次取数组中间的值比如m作为当前节点，m前面的值作为他左子树的结点值，m后面的值作为他右子树的节点值
     * */
    public TreeNode suboper(int[] nums,int left,int right){
        if (left>right)
            return null;
        int mid=left+(right-left)/2;
        TreeNode node=new TreeNode(nums[mid]);
        node.left=suboper(nums,left,mid-1);
        node.right=suboper(nums,mid+1,right);
        return node;
    }
    public TreeNode sortedArrayToBST(int[] nums) {
        if (nums.length==0)
            return null;
        return suboper(nums,0,nums.length-1);
    }

    public static void main(String[] args) {
        TreeNode root=new TreeNode(1,new TreeNode(2,new TreeNode(3),new TreeNode(4)),new TreeNode(2,new TreeNode(4),new TreeNode(3)));
        int[] nums=new int[]{-10,-3,0,5,9};

        Solution_4tree object=new Solution_4tree();
//        System.out.println(object.maxDepth(root));
//        System.out.println(object.isValidBST(root));
//        object.midOrder(root);
//        System.out.println(object.isSymmetric(root));
//        System.out.println(object.levelOrder(root).toString());
        TreeNode res=object.sortedArrayToBST(nums);
        object.midOrder(res);


    }
}
